Hierarchical Navigable Small World
perplexity.ai.icon
Hierarchical Navigable Small World（HNSW）は、高次元データ向けの近似最近傍探索（ANN）を効率的に行うグラフベースのアルゴリズムです。2016年に提案され、大規模なベクトルデータベースやAI応用で広く利用されています。
基本構造
階層的なグラフ構造が特徴で、以下の3層で構成されます：
最上位層：疎な接続（「新幹線」のような長距離リンク）
中間層：中距離リンク（「地下鉄」レベルの接続）
最下位層：密な接続（「徒歩」レベルの詳細リンク）
各データポイントは確率的に階層に配置され、上位層ほどノード数が少なくなります。
検索プロセス
1. 最上位層から開始：ランダムなエントリポイントを選択
2. グリーディ探索：クエリに近いノードへジャンプを繰り返す
3. 階層を降下：局所最適解に到達したら下位層に移動
4. 最下層で精密検索：近似最近傍を最終決定
table:従来手法との比較
特徴 HNSWの優位性
検索速度 階層構造で従来比10-100倍高速
メモリ効率 動的インデックス構築が可能
スケーラビリティ 10億規模のデータでも対応可能
パラメータ調整 層数・接続数(M)で精度/速度を最適化
主な応用分野
推薦システム：ユーザーの嗜好に合うアイテム検索
画像認識：類似画像の高速検索
自然言語処理：Retrieval-Augmented Generation（RAG）での文書検索
HNSWは「スモールワールド」現象（6次の隔たり理論）をアルゴリズム化したもので、現実世界のネットワーク特性を活用することで、高次元データの探索問題を効率的に解決します。検索精度と速度のバランスに優れ、大規模データ時代の基盤技術として注目されています。
おーそういうことかmtane0412.icon
スモールワールド実験